import java.util.*;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/3/23
 * \* Time: 9:40
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class TestDemo {

    public boolean checkWon(int[][] board) {
        int size=board.length;
        int sum=0;
        int i=0;
        int j=0;
//检查每一行的个数是否为size
        for(i=0;i<size;i++){
            for(j=0;j<size;j++){
                sum+=board[i][j];
            }
            if(sum==size){
                return true;
            }
        }
        //检查每一列的个数是否为size
        for(i=0;i<size;i++){
            sum=0;
            for(j=0;j<size;j++){
                sum+=board[j][i];
            }
            if(size==sum){
                return true;
            }
        } //检查主对角线的值
                sum=0;
        for( i=0;i<size;i++){
            sum+=board[i][i];
        }if(size==sum){
            return true;
        }
        //检查副对角线的值
               sum=0;
        for(i=0;i<size;i++){
            sum+=board[i][size-i-1];
        }
        if(size==sum){
            return true;
        }
        return false;
    }


        public static void main32(String[] args){
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine();
            int len = str.length();
            int count = 0;
            if(len<= 4){
                count = 5;
            }else if(len>=5 && len <=7){
                count = 10;
            }else{
                count = 25;
            }

            char[] ch = str.toCharArray();

            for(int i = 0;i<ch.length;i++){
                if(ch[i]>'a' && ch[i]<'z'){
                    count += 10;
                }else if(ch[i] >'A' && ch[i] <'Z'){
                    count +=10;
                }else if(ch[i]>'a' && ch[i]<'z' &&ch[i] >'A' && ch[i] <'Z'){
                    count+=20;
                }else {
                    count+=0;
                }

            }

            add(count);

        }

        public static void add(int count){
            if(count>=80){
                System.out.println("VERY_SECURE");
            }else if(count >= 70){
                System.out.println("SECURE");
            }else if(count >= 60){
                System.out.println("VERY_STRONG");
            }else if(count >= 50){
                System.out.println("AVERAGE");
            }else if(count >= 25){
                System.out.println("WEAK");
            }else{
                System.out.println("VERY_WEAK");
            }
        }




    private static Object myLock1 = new Object();
    private static Object myLock2 = new Object();

    private static Boolean t1Run = false;
    private static Boolean t2Run = false;
    public static void main31(String[] args) {
        final Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                synchronized (myLock1){
                    System.out.println("thread1");
                    t1Run = true;
                    myLock1.notify();
                }
            }
        });

        final Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                synchronized (myLock1){
                    if(!t1Run){
                        System.out.println("thread2");
                        myLock1.notify();
                    }
                }
            }
        });

        final Thread thread3 = new Thread(new Runnable() {
            @Override
            public void run() {
                synchronized (myLock2){
                    if(!t2Run){
                        System.out.println("thread3");
                    }
                }
            }
        });
        thread3.start();
        thread2.start();
        thread1.start();
    }



    public static void main23(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        if(a < b){
            int tmp =a;
            a = b;
            b = tmp;
        }
        int ret =gcb( a, b);
        System.out.println(ret);
    }
    public static int gcb(int a,int b){
        while(b != 0){
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }


    public static void main25(String[] args) {
        String x = "fmn";
        x.toUpperCase();
        String y = x.replace('f','F');
        y = y+"wxy";
        System.out.println(y);
    }


    public static void main24(String[] args){
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();
        int count = 0;//计数器，初始化为0
        int[][]array = new int[w][h];
        for(int i =0;i<w;i++){
            for(int j =0;j < h;j++){
                if(array[i][j] == 0){
                    count++;
                    if(i + 2 < w){
                        array[i+2][j] = 1;
                    }
                    if(j + 2 < h){
                        array[i][j+2] = 1;
                    }
                }
            }
        }
    }




    public static void main21(String[] args) {

        Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("1");
            }
        });
        t.start();
        System.out.println("2");

    }

    public static void main20(String[] args) {
        boolean b = true ? false : true ==true?false:true;
        System.out.println(b);
    }

    public int MoreThanHalfNum_Solution1(int [] array) {
        if(array == null){
            return 0;
        }
        int target = array[0];
        int times = 1;
        for(int i = 1; i < array.length; i++){
            if(times == 0){
                target = array[i];
                times = 1;
            } else if(array[i] == target){
                times++;
            } else{
                times--;
            }
        }
        times = 0;
        for(int i = 0; i < array.length; i++){
            if(target == array[i]){
                times++;
            }
        }
        return times > array.length/2 ? target : 0;
    }

    public static void main18(String[] args) {

    }



        public static void main17(String[] args){
            Scanner sc=new Scanner(System.in);
            String A=sc.nextLine();
            String B=sc.nextLine();
            int count=0;
            for(int i=0;i<=A.length();i++){
                StringBuffer strBuf=new StringBuffer(A);
                //将字符串B插入A的第i个位置
                strBuf.insert(i,B);
                String str1=new String(strBuf);
                strBuf.reverse();
                //判断是否是回文
                if(str1.equals(strBuf.toString())){
                    count++;
                }
            }
            System.out.println(count);
        }

    public static void main16(String [] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        //采用StringBuffer
        int ans = 0;
        for(int i =0 ; i <=str1.length();i++){
            StringBuffer strBuffer = new StringBuffer(str1);
            //insert
            strBuffer.insert(i,str2);

            String str = new String(strBuffer);
            strBuffer.reverse();
            if(str.equals(strBuffer.toString())){
                ans++;
            }
        }
        System.out.println(ans);
    }


    public static void main15(String [] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        //先将字符串转换成字符数组进行插入，还是可以直接插入？
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        char[] array = new char[ch1.length+ch2.length];
        for (int i = 0; i < array.length; i++) {

        }



    }
    public static boolean isHuiwen(char[] array){
        int i = 0;
        int len = array.length - 1;
        int j = len;
        boolean flag = true;
        while(i <= j){
            if(array[i] == array[j]){
                i++;
                j--;
                flag = true;
            }else{
                flag = false;
                break;
            }
        }
        return flag;
    }


    public static void reverse(char[] array,int start,int end){
        while(start < end){
            char tmp = array[start];
            array[start] = array[end];
            array[end] = tmp;
            start++;
            end--;
        }
    }

    public static void main13(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        char [] array = str.toCharArray();
        int len = array.length;
        reverse(array,0,len-1);
        int i =0;
        while ( i < len ){
            int j = i;
            //hello world
            //dlrow olleh
            //i
            //     j
            //      i
            //          j
            //          i
            while(j < len && array[j] != ' '){
                j++;
            }
            if(j < len){
                reverse(array,i,j-1);
                i = j+1;
            }else{
                reverse(array,i,j-1);
                i = j;
            }
        }
        String str1 = new String(array);//???
        System.out.println(array);

    }

    public static void main12(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int []arr = new int[n+1];
        for(int i = 0;i < n; i++){
            arr[i] = sc.nextInt();
        }
        int start = 0;
        int ans = 0;
        while(start < n){
            if(arr[start]>arr[start+1]){
                while(start < n && arr[start]>arr[start+1]){
                    start++;
                }
                ans++;
                start++;
            }else if(arr[start] == arr[start+1]){
                start++;
            }else{
                while(start < n && arr[start] < arr[start+1]){
                    start++;
                }
                ans++;
                start++;
            }
        }
        System.out.println(ans);
    }

    public static void main9(String[] args){
        Scanner sc = new Scanner(System.in);
        //10/2 = 0
        //5/2=1
        //2/2=0
        //1/2=1   1010=1*2^3+1*2^1=10

        //10/3 = 1
        //3/3=0
        //1/3=1  301= 1*3^2+1*3^0=10
        int M = sc.nextInt();
        int N = sc.nextInt();
        List <Integer> list = new ArrayList<>();
        while (M>=1){
            list.add(M%N);
            M = M/N;
        }
        Stack stack = new Stack();
        for (int i = 0; i < list.size(); i++) {
            stack.push(list.remove(i));
        }
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }


    public static void main11(String[] args) {
        int A, B, C;
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[4];
        for (int i = 0; i < 4; i++) {
            arr[i] = scanner.nextInt();
        }
        candy(arr);
    }
    public static void candy(int []array){
        int A =(array[0] +array[2])/2;
        int B1 = (array[1] +array[3])/2;
        int B2 = (array[2] - array[0])/2;
        if(B1 != B2){
            System.out.println("No");
            return;
        }
        int C = (array[3]-array[1])/2;
        System.out.println(A+" "+B1 +""+C);
    }


    public static void main8(String[] args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        StringBuffer buffer=new StringBuffer();
        for(int i=0;i<str1.length();i++){
            if(!str2.contains(str1.charAt(i)+"")){
                buffer.append(str1.charAt(i));
            }
        }
        System.out.println(buffer.toString());
    }

    public static void main7(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i =0;i<str2.length();i++){
            if(map.get(str2.charAt(i))==null){
                map.put(str2.charAt(i),1);
            }else{
                map.put(str2.charAt(i),map.get(str2.charAt(i)));
            }
        }
        String ret = "";
        for(int i =0;i<str1.length();i++){
            if(map.get(str1.charAt(i))==null){
                ret += str1.charAt(i);
            }
        }
        System.out.println(ret);
    }



    public static void main5(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        Set<Character> map = new HashSet<>();
        for(int i = 0;i<str1.length();i++){
            map.add(str1.charAt(i));
        }
        List<Character> list = new ArrayList<>();
        for(int i =0;i<str2.length();i++){
            if(!map.contains(str2.charAt(i))){
                list.add(str2.charAt(i));
            }
        }
        System.out.println(list);

    }


    public static void main2(String[] args){
        Set<Character> map = new HashSet<>();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long sum = 0;
        int []array = new int[3*n];
        for(int i =0;i<array.length;i++){
            array[i] = scanner.nextInt();
        }
        Arrays.sort(array);
        for(int i=0; i < n ;i++){
            sum += array[array.length - 2*(i+1)];

        }
        System.out.println(sum);
    }

    private Map<Integer, Integer> filter = new HashMap<>();
    public int Fibonacci(int n) {
        if(n == 0 || n == 1){
            return n;
        }
// filter = new HashMap<>();
        int pre = 0;
        if(filter.containsKey(n-1)){
            pre = filter.get(n-1);
        } else{
            pre = Fibonacci(n-1);
            filter.put(n-1, pre);
        }
        int ppre = 0;
        if(filter.containsKey(n-2)){
            ppre = filter.get(n-2);
        } else{
            ppre = Fibonacci(n-2);
            filter.put(n-2, ppre);
        }
        return pre + ppre;
    }

    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int nums : array){
            map.put(nums, map.getOrDefault(nums,0)+1);
        }
        for (int nums : array){
            if(map.get(nums) > array.length/2){
                return nums;
            }
        }
        return 0;
    }


    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String res = "";
        char[] array = str.toCharArray();
        //将字符串转化为字符数组，然后遍历里面的元素
        int ans = 0;
        for(int i = 0; i < array.length; i++){
            if(Character.isDigit(array[i])){
                ans = 1;
                int index = i;
                for(int j = i;j<array.length; j++){
                    if(Character.isDigit(array[j])){
                        index = j;
                        ans++;
                    }else{
                        break;
                    }
                }
                if(ans > res.length()){
                    res = str.substring(i,index + 1);
                }
            }

        }
        System.out.println(res);
    }

}
